#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

class Function
{
public:
    virtual double operator()(double x) = 0;
};

class Newton
{
private:
    int n;
    vector<double> x;
    vector<double> y;
    vector<vector<double>> table;
public:
    Newton();
    Newton(vector<double> x1, vector<double> y1) :x(x1), y(y1)
    {
        n = x.size();
        table = DifferenceQuotient();
    }
    vector<vector<double>> DifferenceQuotient()
    {
        vector<vector<double>> table(n);
        for (int i = 0;i < n;i++)
        {
            table[i].resize(n);
        }
        for (int j = 0;j < n;j++)
        {
            for (int i = 0;i < n;i++)
            {
                if (i >= j)
                {
                    if (j == 0)
                    {
                        table[i][j] = y[i];
                    }
                    else
                    {
                        table[i][j] = (table[i - 1][j - 1] - table[i][j - 1]) / (x[i - j] - x[i]);
                    }
                }
            }
        }
        return table;
    }

    double getY(int i) 
    {
        return y[i];
    }
    double getX(int i)
    {
        return x[i];
    }

    double getTable(int i, int j)
    {
        return table[i][j];
    }
    void output()
    {
        cout << "     x = [";
        for (int i = 0;i < n;i++)
        {
            cout << x[i];
            if (i < (n - 1))
                cout << ",";
        }
        cout << "]" << endl;

        for (int i = 0;i < n;i++)
        {
            cout << "     f[";
            for (int j = 0;j <= i;j++)
            {
                cout << "x" << j;
                if (j < i)
                    cout << ",";
            }
            cout << "]=" << table[i][i] << " ";
        }
        cout << endl;

        cout << "     The resulting polynomial is" << endl;
        cout << "     p(x)=";
        for (int i = 0;i < n;i++)
        {
            if (abs(table[i][i]) != 1)
            {
                cout << abs(table[i][i]);
                if (i != 0)
                    cout << "*";
            }
            for (int j = 0;j < i;j++)
            {
                if (x[j] < 0)
                {
                    cout << "(x+" << -x[j] << ")";
                }
                else if (x[j] == 0)
                {
                    cout << "x";
                }
                else
                {
                    cout << "(x-" << x[j] << ")";
                }
                if (j < (i - 1))
                    cout << "*";
            }
            if (i < (n - 1))
            {
                if (table[i + 1][i + 1] >= 0)
                    cout << "+";
                else
                    cout << "-";
            }
        }
        cout << endl;
    }
};


